package com.boyue.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

//一致性iphash算法
public class IpHash {
    public static String routeServer(List<String> servers, String node){
        //节点机器ip servers
        // 使用SortedMap可以排序，再使用tailMap获取key比hashCode[client_ip]大的子map
        //Tnteger--》hashCode值，String---》虚拟节点名称
        SortedMap virtualNodes= new TreeMap<Integer, String>();
        //虚拟节点数目
        int VIRTUAL_NODE_NUM = 4;
        for (int i = 0, len = servers.size() ; i < len; i++){
        int hashCode;
        String vitualNode;
        for (int j = 0; j < VIRTUAL_NODE_NUM; j++) {
            // 计算节点的哈希值作为key，节点ip("168.10.10.101:6386vni")作为value
            vitualNode = servers.get(i) + "vn" + j;
            // 计算虚拟节点的hashCode
            hashCode = getHashCode(vitualNode);
            virtualNodes.putIfAbsent(hashCode, vitualNode);
            }
        }

        //通过client_ip的哈希值路由一个虚拟节点，再映射到物理节点
        int hashCode = getHashCode(node);
        //找到key大于hashcode值的map集合
        SortedMap subMap = virtualNodes.tailMap(hashCode);
        int firstKey;
        String virtualNodeName;
        if(subMap.isEmpty()){
            //没找到的话就是第一个key
            firstKey=(Integer)virtualNodes.firstKey();
            virtualNodeName=(String)virtualNodes.get(firstKey);
        }else {
            firstKey=(Integer)subMap.firstKey();
            virtualNodeName=(String)virtualNodes.get(firstKey);
        }
//        int firstKey =(Integer) (subMap.isEmpty()?virtualNodes.firstKey():subMap.firstKey());
//        String virtualNode = (String)(subMap.isEmpty()?virtualNodes.get(firstKey):subMap.get(firstKey));
        // 模拟寻找物理节点，把vni去掉
        String actualNode = virtualNodeName.substring(0, virtualNodeName.length() - 3);
        System.out.println(node + "的hashCode为" + hashCode + "，被路由到虚拟节点："
                + virtualNodeName + "，映射到物理节点：" + actualNode);
        return actualNode;
    }

    public static void main(String[] args) {
        List<String> serverS=new ArrayList<>();
        serverS.add("192.168.43.85:8761");
        serverS.add("192.168.43.85:8001");
        serverS.add("192.168.43.85:8002");
        serverS.add("192.168.43.85:8003");
        serverS.add("192.168.43.85:8004");
        List<String> clientS=new ArrayList<>();
        clientS.add("193.168.333.2");
        clientS.add("193.168.222.2");
        clientS.add("193.168.222.2");
        clientS.add("193.168.333.111");
        clientS.add("193.168.333.111");
        for(int i=0;i<clientS.size();i++){
            String item = clientS.get(i);
            String ip= routeServer(serverS, item);
            System.out.println("返回的服务信息:"+ip);
        }
    }



    // 使用32位FNV_1计算节点的hashCode
    public static int getHashCode(String node) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < node.length(); i++)
            hash = (hash ^ node.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        // 如果算出来的值为负数则取其绝对值
        if (hash < 0){
            hash = Math.abs(hash);
        }
        //直接使用hashCode出来的值，在环上分布不均
//        return node.hashCode()&Integer.MAX_VALUE;
        return hash;
    }
}

//"D:\Program Files\Java\jdk1.8.0_65\bin\java.exe" "-javaagent:G:\development\JetBrains\IntelliJ IDEA 2018.3.5\lib\idea_rt.jar=54590:G:\development\JetBrains\IntelliJ IDEA 2018.3.5\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_65\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_65\jre\lib\rt.jar;E:\idea\springboot2020\SpringCloud-Project\eureka-client\target\classes;D:\mymavenlib\repository\org\springframework\boot\spring-boot-starter-web\2.1.6.RELEASE\spring-boot-starter-web-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-starter\2.1.6.RELEASE\spring-boot-starter-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot\2.1.6.RELEASE\spring-boot-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-autoconfigure\2.1.6.RELEASE\spring-boot-autoconfigure-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-starter-logging\2.1.6.RELEASE\spring-boot-starter-logging-2.1.6.RELEASE.jar;D:\mymavenlib\repository\ch\qos\logback\logback-classic\1.2.3\logback-classic-1.2.3.jar;D:\mymavenlib\repository\ch\qos\logback\logback-core\1.2.3\logback-core-1.2.3.jar;D:\mymavenlib\repository\org\apache\logging\log4j\log4j-to-slf4j\2.11.2\log4j-to-slf4j-2.11.2.jar;D:\mymavenlib\repository\org\apache\logging\log4j\log4j-api\2.11.2\log4j-api-2.11.2.jar;D:\mymavenlib\repository\org\slf4j\jul-to-slf4j\1.7.26\jul-to-slf4j-1.7.26.jar;D:\mymavenlib\repository\javax\annotation\javax.annotation-api\1.3.2\javax.annotation-api-1.3.2.jar;D:\mymavenlib\repository\org\springframework\spring-core\5.1.8.RELEASE\spring-core-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\springframework\spring-jcl\5.1.8.RELEASE\spring-jcl-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\yaml\snakeyaml\1.23\snakeyaml-1.23.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-starter-json\2.1.6.RELEASE\spring-boot-starter-json-2.1.6.RELEASE.jar;D:\mymavenlib\repository\com\fasterxml\jackson\core\jackson-databind\2.9.9\jackson-databind-2.9.9.jar;D:\mymavenlib\repository\com\fasterxml\jackson\datatype\jackson-datatype-jdk8\2.9.9\jackson-datatype-jdk8-2.9.9.jar;D:\mymavenlib\repository\com\fasterxml\jackson\datatype\jackson-datatype-jsr310\2.9.9\jackson-datatype-jsr310-2.9.9.jar;D:\mymavenlib\repository\com\fasterxml\jackson\module\jackson-module-parameter-names\2.9.9\jackson-module-parameter-names-2.9.9.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-starter-tomcat\2.1.6.RELEASE\spring-boot-starter-tomcat-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\apache\tomcat\embed\tomcat-embed-core\9.0.21\tomcat-embed-core-9.0.21.jar;D:\mymavenlib\repository\org\apache\tomcat\embed\tomcat-embed-el\9.0.21\tomcat-embed-el-9.0.21.jar;D:\mymavenlib\repository\org\apache\tomcat\embed\tomcat-embed-websocket\9.0.21\tomcat-embed-websocket-9.0.21.jar;D:\mymavenlib\repository\org\hibernate\validator\hibernate-validator\6.0.17.Final\hibernate-validator-6.0.17.Final.jar;D:\mymavenlib\repository\javax\validation\validation-api\2.0.1.Final\validation-api-2.0.1.Final.jar;D:\mymavenlib\repository\org\jboss\logging\jboss-logging\3.3.2.Final\jboss-logging-3.3.2.Final.jar;D:\mymavenlib\repository\com\fasterxml\classmate\1.4.0\classmate-1.4.0.jar;D:\mymavenlib\repository\org\springframework\spring-web\5.1.8.RELEASE\spring-web-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\springframework\spring-beans\5.1.8.RELEASE\spring-beans-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\springframework\spring-webmvc\5.1.8.RELEASE\spring-webmvc-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\springframework\spring-aop\5.1.8.RELEASE\spring-aop-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\springframework\spring-context\5.1.8.RELEASE\spring-context-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\springframework\spring-expression\5.1.8.RELEASE\spring-expression-5.1.8.RELEASE.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-starter-netflix-eureka-client\2.1.0.RELEASE\spring-cloud-starter-netflix-eureka-client-2.1.0.RELEASE.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-starter\2.1.1.RELEASE\spring-cloud-starter-2.1.1.RELEASE.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-context\2.1.1.RELEASE\spring-cloud-context-2.1.1.RELEASE.jar;D:\mymavenlib\repository\org\springframework\security\spring-security-crypto\5.1.5.RELEASE\spring-security-crypto-5.1.5.RELEASE.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-commons\2.1.1.RELEASE\spring-cloud-commons-2.1.1.RELEASE.jar;D:\mymavenlib\repository\org\springframework\security\spring-security-rsa\1.0.7.RELEASE\spring-security-rsa-1.0.7.RELEASE.jar;D:\mymavenlib\repository\org\bouncycastle\bcpkix-jdk15on\1.60\bcpkix-jdk15on-1.60.jar;D:\mymavenlib\repository\org\bouncycastle\bcprov-jdk15on\1.60\bcprov-jdk15on-1.60.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-netflix-hystrix\2.1.1.RELEASE\spring-cloud-netflix-hystrix-2.1.1.RELEASE.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-starter-aop\2.1.6.RELEASE\spring-boot-starter-aop-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\aspectj\aspectjweaver\1.9.4\aspectjweaver-1.9.4.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-netflix-eureka-client\2.1.1.RELEASE\spring-cloud-netflix-eureka-client-2.1.1.RELEASE.jar;D:\mymavenlib\repository\com\netflix\eureka\eureka-client\1.9.8\eureka-client-1.9.8.jar;D:\mymavenlib\repository\org\codehaus\jettison\jettison\1.3.7\jettison-1.3.7.jar;D:\mymavenlib\repository\stax\stax-api\1.0.1\stax-api-1.0.1.jar;D:\mymavenlib\repository\com\netflix\netflix-commons\netflix-eventbus\0.3.0\netflix-eventbus-0.3.0.jar;D:\mymavenlib\repository\com\netflix\netflix-commons\netflix-infix\0.3.0\netflix-infix-0.3.0.jar;D:\mymavenlib\repository\commons-jxpath\commons-jxpath\1.3\commons-jxpath-1.3.jar;D:\mymavenlib\repository\joda-time\joda-time\2.10.2\joda-time-2.10.2.jar;D:\mymavenlib\repository\org\antlr\antlr-runtime\3.4\antlr-runtime-3.4.jar;D:\mymavenlib\repository\org\antlr\stringtemplate\3.2.1\stringtemplate-3.2.1.jar;D:\mymavenlib\repository\antlr\antlr\2.7.7\antlr-2.7.7.jar;D:\mymavenlib\repository\com\google\code\gson\gson\2.8.5\gson-2.8.5.jar;D:\mymavenlib\repository\org\apache\commons\commons-math\2.2\commons-math-2.2.jar;D:\mymavenlib\repository\com\netflix\archaius\archaius-core\0.7.6\archaius-core-0.7.6.jar;D:\mymavenlib\repository\com\google\guava\guava\16.0\guava-16.0.jar;D:\mymavenlib\repository\javax\ws\rs\jsr311-api\1.1.1\jsr311-api-1.1.1.jar;D:\mymavenlib\repository\com\netflix\servo\servo-core\0.12.21\servo-core-0.12.21.jar;D:\mymavenlib\repository\com\sun\jersey\jersey-core\1.19.1\jersey-core-1.19.1.jar;D:\mymavenlib\repository\com\sun\jersey\jersey-client\1.19.1\jersey-client-1.19.1.jar;D:\mymavenlib\repository\com\sun\jersey\contribs\jersey-apache-client4\1.19.1\jersey-apache-client4-1.19.1.jar;D:\mymavenlib\repository\org\apache\httpcomponents\httpclient\4.5.9\httpclient-4.5.9.jar;D:\mymavenlib\repository\org\apache\httpcomponents\httpcore\4.4.11\httpcore-4.4.11.jar;D:\mymavenlib\repository\commons-codec\commons-codec\1.11\commons-codec-1.11.jar;D:\mymavenlib\repository\com\google\inject\guice\4.1.0\guice-4.1.0.jar;D:\mymavenlib\repository\javax\inject\javax.inject\1\javax.inject-1.jar;D:\mymavenlib\repository\aopalliance\aopalliance\1.0\aopalliance-1.0.jar;D:\mymavenlib\repository\com\github\vlsi\compactmap\compactmap\1.2.1\compactmap-1.2.1.jar;D:\mymavenlib\repository\com\github\andrewoma\dexx\dexx-collections\0.2\dexx-collections-0.2.jar;D:\mymavenlib\repository\com\fasterxml\jackson\core\jackson-annotations\2.9.0\jackson-annotations-2.9.0.jar;D:\mymavenlib\repository\com\fasterxml\jackson\core\jackson-core\2.9.9\jackson-core-2.9.9.jar;D:\mymavenlib\repository\com\netflix\eureka\eureka-core\1.9.8\eureka-core-1.9.8.jar;D:\mymavenlib\repository\org\codehaus\woodstox\woodstox-core-asl\4.4.1\woodstox-core-asl-4.4.1.jar;D:\mymavenlib\repository\javax\xml\stream\stax-api\1.0-2\stax-api-1.0-2.jar;D:\mymavenlib\repository\org\codehaus\woodstox\stax2-api\3.1.4\stax2-api-3.1.4.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-starter-netflix-archaius\2.1.1.RELEASE\spring-cloud-starter-netflix-archaius-2.1.1.RELEASE.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-netflix-ribbon\2.1.1.RELEASE\spring-cloud-netflix-ribbon-2.1.1.RELEASE.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-netflix-archaius\2.1.1.RELEASE\spring-cloud-netflix-archaius-2.1.1.RELEASE.jar;D:\mymavenlib\repository\commons-configuration\commons-configuration\1.8\commons-configuration-1.8.jar;D:\mymavenlib\repository\commons-lang\commons-lang\2.6\commons-lang-2.6.jar;D:\mymavenlib\repository\org\springframework\cloud\spring-cloud-starter-netflix-ribbon\2.1.1.RELEASE\spring-cloud-starter-netflix-ribbon-2.1.1.RELEASE.jar;D:\mymavenlib\repository\com\netflix\ribbon\ribbon\2.3.0\ribbon-2.3.0.jar;D:\mymavenlib\repository\com\netflix\ribbon\ribbon-transport\2.3.0\ribbon-transport-2.3.0.jar;D:\mymavenlib\repository\io\reactivex\rxnetty-contexts\0.4.9\rxnetty-contexts-0.4.9.jar;D:\mymavenlib\repository\io\reactivex\rxnetty-servo\0.4.9\rxnetty-servo-0.4.9.jar;D:\mymavenlib\repository\com\netflix\hystrix\hystrix-core\1.5.18\hystrix-core-1.5.18.jar;D:\mymavenlib\repository\io\reactivex\rxnetty\0.4.9\rxnetty-0.4.9.jar;D:\mymavenlib\repository\com\netflix\ribbon\ribbon-core\2.3.0\ribbon-core-2.3.0.jar;D:\mymavenlib\repository\com\netflix\ribbon\ribbon-httpclient\2.3.0\ribbon-httpclient-2.3.0.jar;D:\mymavenlib\repository\commons-collections\commons-collections\3.2.2\commons-collections-3.2.2.jar;D:\mymavenlib\repository\com\netflix\netflix-commons\netflix-commons-util\0.3.0\netflix-commons-util-0.3.0.jar;D:\mymavenlib\repository\com\netflix\ribbon\ribbon-loadbalancer\2.3.0\ribbon-loadbalancer-2.3.0.jar;D:\mymavenlib\repository\com\netflix\netflix-commons\netflix-statistics\0.1.1\netflix-statistics-0.1.1.jar;D:\mymavenlib\repository\io\reactivex\rxjava\1.3.8\rxjava-1.3.8.jar;D:\mymavenlib\repository\com\netflix\ribbon\ribbon-eureka\2.3.0\ribbon-eureka-2.3.0.jar;D:\mymavenlib\repository\org\slf4j\slf4j-api\1.7.26\slf4j-api-1.7.26.jar;D:\mymavenlib\repository\com\thoughtworks\xstream\xstream\1.4.10\xstream-1.4.10.jar;D:\mymavenlib\repository\xmlpull\xmlpull\1.1.3.1\xmlpull-1.1.3.1.jar;D:\mymavenlib\repository\xpp3\xpp3_min\1.1.4c\xpp3_min-1.1.4c.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-starter-actuator\2.1.6.RELEASE\spring-boot-starter-actuator-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-actuator-autoconfigure\2.1.6.RELEASE\spring-boot-actuator-autoconfigure-2.1.6.RELEASE.jar;D:\mymavenlib\repository\org\springframework\boot\spring-boot-actuator\2.1.6.RELEASE\spring-boot-actuator-2.1.6.RELEASE.jar;D:\mymavenlib\repository\io\micrometer\micrometer-core\1.1.5\micrometer-core-1.1.5.jar;D:\mymavenlib\repository\org\hdrhistogram\HdrHistogram\2.1.9\HdrHistogram-2.1.9.jar;D:\mymavenlib\repository\org\latencyutils\LatencyUtils\2.0.3\LatencyUtils-2.0.3.jar" com.boyue.algorithm.IpHash
//        193.168.333.2的hashCode为524895031，被路由到虚拟节点：192.168.43.85:8001vn0，映射到物理节点：192.168.43.85:8001
//        返回的服务信息:192.168.43.85:8001
//        193.168.222.2的hashCode为609627807，被路由到虚拟节点：192.168.43.85:8002vn3，映射到物理节点：192.168.43.85:8002
//        返回的服务信息:192.168.43.85:8002
//        193.168.222.2的hashCode为609627807，被路由到虚拟节点：192.168.43.85:8002vn3，映射到物理节点：192.168.43.85:8002
//        返回的服务信息:192.168.43.85:8002
//        193.168.333.111的hashCode为847167189，被路由到虚拟节点：192.168.43.85:8761vn1，映射到物理节点：192.168.43.85:8761
//        返回的服务信息:192.168.43.85:8761
//        193.168.333.111的hashCode为847167189，被路由到虚拟节点：192.168.43.85:8761vn1，映射到物理节点：192.168.43.85:8761
//        返回的服务信息:192.168.43.85:8761
//
//        Process finished with exit code 0


